package leetcode.dfs;

//547. 省份数量
public class FindCircleNum {
    public static void main(String[] args) {

        System.out.println(findCircleNum(new int[][]{{1, 0, 1}, {0, 1, 1}, {1, 1, 1}}));
    }

    //DFS
    public static int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(isConnected, visited, i, n);
                res++;
            }
        }
        return res;
    }

    private static void dfs(int[][] isConnected, boolean[] visited, int i, int n) {
        for (int j = 0; j < n; j++) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                visited[j] = true;
                dfs(isConnected, visited, j, n);
            }
        }
    }

    // 二战
    public int findCircleNumP(int[][] isConnected) {
        int res = 0;
        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        for (int i = 0; i < isConnected.length; i++) {
            if (!visited[i]) {
                dfs2(isConnected, visited, i, n);
                res++;
            }
        }
        return res;
    }

    private void dfs2(int[][] isConnected, boolean[] visited, int x, int n) {
        for (int i = 0; i < n; i++) {
            if (isConnected[x][i]==1 && !visited[i]){
                visited[i] = true;
                dfs2(isConnected,visited,i,n);
            }
        }
    }
}
